package com.kevinkk.greedy;

/**
 * 当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
 * 给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
 */

public class MonotoneIncreasingDigits {
    class Solution {
        public int monotoneIncreasingDigits(int n) {
            char[] c = (n + "").toCharArray();
            // 用 flag 来记录从赋值9从哪里开始
            // 一旦一个位置需要改写为 9，它后面所有的值都需要改为9（例如 100 需要改写为 99，而不是190）
            int flag = c.length;
            for (int i = c.length - 2; i >= 0; i--) {
                if (c[i] > c[i + 1]) {
                    c[i] = (char) (c[i] - 1);
                    flag = i + 1;
                }
            }

            for (int i = flag; i < c.length; i++) {
                c[i] = '9';
            }

            return Integer.parseInt(new String(c));
        }
    }
}
